#include <../includes/libalgorithm.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <string>
#include <algorithm>
#include <sstream>
#include <fstream>
#include <limits>
#include <cassert>
#include <utility> 

std::unordered_map<std::string, std::vector<BusLine>> BusSystem::routes; 

// 查询公交线路详情
std::string BusSystem::algorithm::queryBusLineDetails(const std::string& lineName) 
{
    std::string echo;
    std::stringstream ss;

    bool found = false;
    for (const auto& routePair : BusSystem::routes) 
    {
        for (const auto& line : routePair.second) 
        {
            if (line.lineName == lineName) 
            {
                found = true;
                ss << "线路 " << lineName << " 的详细信息:\n";
                for (const auto& stop : line.stations) 
                {
                    ss << stop << " ";
                }
                ss << "\n首班车时间: " << line.firstBusTime << ", 末班车时间: " << line.lastBusTime << "\n";
                echo = ss.str();
                return echo;
            }
        }
    }

    if (!found) 
    {
        ss << "未找到该线路。\n";
    }
    echo = ss.str();
    return echo;
}

// 查询两站之间的路线
std::string BusSystem::algorithm::queryRoutesBetweenStops(const std::string& start, const std::string& end) 
{
    std::string echo;
    std::stringstream ss;

    // 检查两个站点是否存在于系统中
    if (BusSystem::routes.find(start) == BusSystem::routes.end() || BusSystem::routes.find(end) == BusSystem::routes.end()) 
    {
        ss << "无效的站点，请检查输入。\n";
        echo = ss.str();
        return echo;
    }

    // 1. 首先查找直达路线
    ss << BusSystem::algorithm::findDirectRoutes(start, end);
    
    // 2. 如果没有直达路线，则搜索换乘路线
    ss << BusSystem::algorithm::findOptimalRoute(start, end);  // 查找最少换乘次数的路线
    ss << BusSystem::algorithm::findShortestTimeRoute(start, end);  // 查找最短时间的路线
    echo = ss.str();
    return echo;
}

std::string BusSystem::algorithm::findAllPossibleRoutes(const std::string& start, const std::string& end) 
{
    std::string echo;
    std::stringstream ss;

    std::vector<std::string> path;
    std::unordered_map<std::string, bool> visited;
    
    // 初始化所有站点的访问状态为未访问
    for (const auto& route : BusSystem::routes) {
        visited[route.first] = false;
    }

    ss << "所有从 " << start << " 到 " << end << " 的可行路线:\n";
    BusSystem::algorithm::dfs(start, end, visited, path, ss);
    
    echo = ss.str();
    return echo;
}

// 递归实现深度优先搜索
void BusSystem::algorithm::dfs(const std::string& current, const std::string& end, 
         std::unordered_map<std::string, bool>& visited, std::vector<std::string>& path, 
                            std::stringstream& ss) 
{
    visited[current] = true;  // 标记当前站点为已访问
    path.push_back(current);  // 将当前站点添加到路径中

    if (current == end) {
        // 找到一条可行路线，输出路径
        for (const std::string& stop : path) {
            std::cout << stop << " ";
        }
        std::cout << std::endl;
    } else {
        // 遍历当前站点的所有相邻站点
        for (const auto& line : BusSystem::routes[current]) {
            for (size_t i = 0; i < line.stations.size() - 1; ++i) {
                if (line.stations[i] == current && !visited[line.stations[i + 1]]) {
                    // 递归搜索相邻站点
                    BusSystem::algorithm::dfs(line.stations[i + 1], end, visited, path, ss);
                }
            }
        }
    }

    // 回溯：将当前站点标记为未访问并从路径中移除
    visited[current] = false;
    path.pop_back();
}

// 查找并显示所有直达路线（仅考虑旅行时间为正的路线）
std::string BusSystem::algorithm::findDirectRoutes(const std::string& start, const std::string& end) 
{
    std::string echo;
    std::stringstream ss;

    bool foundDirectRoute = false;
    std::vector<std::pair<std::string, int>> directRoutes; // {线路名称, 总时间}

    for (const auto& line : BusSystem::routes[start]) 
    {
        if (std::find(line.stations.begin(), line.stations.end(), end) != line.stations.end()) 
        {
            int totalTime = 0;
            for (size_t i = 0; i < line.stations.size() - 1; ++i) 
            {
                if (line.stations[i] == start) 
                {
                    for (size_t j = i; j < line.stations.size() - 1; ++j) 
                    {
                        int travelTime = line.travelTimes.at({line.stations[j], line.stations[j + 1]});
                        totalTime += travelTime;
                        if (line.stations[j + 1] == end) 
                        {
                            foundDirectRoute = true;
                            break;
                        }
                    }
                    break;
                }
            }
            if (foundDirectRoute) 
            {
                directRoutes.push_back({line.lineName, totalTime});
            }
        }
    }

    if (!directRoutes.empty()) 
    {
        ss << "从 " << start << " 到 " << end << " 的直达路线:\n";
        for (const auto& [name, time] : directRoutes) 
        {
            ss << "线路 " << name << ", 旅行时间: " << time << " 分钟\n";
        }
    } 
    else 
    {
        ss << "未找到从 " << start << " 到 " << end << " 的直达路线。\n";
    }
    echo = ss.str();
    return echo;
}

// 最优换乘算法（BFS）：找到最少站数或最少换乘次数的路径
std::string BusSystem::algorithm::findOptimalRoute(const std::string& start, const std::string& end) 
{
    std::string echo;
    std::stringstream ss;

    using Node = std::tuple<std::string, int, int, std::string, std::vector<std::string>>;  // {当前站, 站数, 换乘次数, 线路名称, 路径}
    std::queue<Node> q;
    std::unordered_map<std::string, bool> visited;

    q.push({start, 0, 0, "", {start}});
    visited[start] = true;

    std::vector<Node> results;

    while (!q.empty()) 
    {
        auto [currentStop, stopCount, transfers, currentLine, path] = q.front();
        q.pop();

        if (currentStop == end) 
        {
            results.push_back({currentStop, stopCount, transfers, currentLine, path});
            continue;
        }

        for (const auto& line : BusSystem::routes[currentStop]) 
        {
            for (size_t i = 0; i < line.stations.size(); ++i) 
            {
                if (line.stations[i] == currentStop && i + 1 < line.stations.size()) 
                {
                    std::string nextStop = line.stations[i + 1];
                    int travelTime = line.travelTimes.at({line.stations[i], nextStop});
                    if (travelTime > 0 && !visited[nextStop]) 
                    {
                        visited[nextStop] = true;
                        int newTransfers = (currentLine != line.lineName) ? transfers + 1 : transfers;
                        std::vector<std::string> newPath = path;
                        newPath.push_back(nextStop);
                        q.push({nextStop, stopCount + 1, newTransfers, line.lineName, newPath});
                    }
                }
            }
        }
    }

    if (results.empty()) 
    {
        ss << "从 " << start << " 到 " << end << " 未找到有效的换乘路线。\n";
        echo = ss.str();
        return echo;
    }

    ss << "从 " << start << " 到 " << end << " 找到的换乘路线:\n";
    for (const auto& [_, stations, transfers, line, path] : results) 
    {
        ss << "路径: ";
        for (const auto& stop : path) ss << stop << " ";
        ss << " | 站数: " << stations << " | 换乘次数: " << transfers << "\n";
    }

    // 显示站数最少的路线
    auto minStops = *std::min_element(results.begin(), results.end(), 
        [](const Node& a, const Node& b) { return std::get<1>(a) < std::get<1>(b); });
    ss << "\n站数最少的路线: ";
    for (const auto& stop : std::get<4>(minStops)) ss << stop << " ";
    ss << " | 站数: " << std::get<1>(minStops) << "\n";

    // 显示换乘次数最少的路线
    auto minTransfers = *std::min_element(results.begin(), results.end(), 
        [](const Node& a, const Node& b) { return std::get<2>(a) < std::get<2>(b); });
    ss << "\n换乘次数最少的路线: ";
    for (const auto& stop : std::get<4>(minTransfers)) std::cout << stop << " ";
    ss << " | 换乘次数: " << std::get<2>(minTransfers) << "\n";
    echo = ss.str();
    return echo;
}

// Dijkstra 算法：找到用时最少的路径
std::string BusSystem::algorithm::findShortestTimeRoute(const std::string& start, const std::string& end) 
{
    std::string echo;
    std::stringstream ss;
    
    using Node = std::tuple<int, std::string, std::vector<std::string>>;  // {Total time, current stop, path}
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;
    std::unordered_map<std::string, int> dist;

    for (const auto& route : BusSystem::routes) dist[route.first] = std::numeric_limits<int>::max();
    dist[start] = 0;

    pq.push({0, start, {start}});

    bool routeFound = false;

    while (!pq.empty()) 
    {
        auto [currentTime, currentStop, path] = pq.top();
        pq.pop();

        if (currentStop == end) 
        {
            ss << "从 " << start << " 到 " << end << " 找到最短时间路线:\n";
            ss << "路径: ";
            for (const auto& stop : path) ss << stop << " ";
            ss << " | 总时间: " << currentTime << " 分钟\n";
            routeFound = true;
            echo = ss.str();
            return echo;
        }

        for (const auto& line : BusSystem::routes[currentStop]) 
        {
            for (size_t i = 0; i < line.stations.size(); ++i) 
            {
                if (line.stations[i] == currentStop && i + 1 < line.stations.size()) 
                {
                    std::string nextStop = line.stations[i + 1];
                    int travelTime = line.travelTimes.at({currentStop, nextStop});

                    if (travelTime > 0 && currentTime + travelTime < dist[nextStop]) 
                    {
                        dist[nextStop] = currentTime + travelTime;
                        std::vector<std::string> newPath = path;
                        newPath.push_back(nextStop);
                        pq.push({dist[nextStop], nextStop, newPath});
                    }
                }
            }
        }
    }

    if (!routeFound) 
    {
        ss << "从 " << start << " 到 " << end << " 未找到有效最短时间路线。\n";
    }
    echo = ss.str();
    return echo;
}

// 打印出routes值
void BusSystem::printRoutes() 
{
    for (const auto& routePair : BusSystem::routes) 
    {
        std::cout << "Route Key: " << routePair.first << std::endl;
        for (const auto& line : routePair.second) 
        {
            std::cout << "Line Name: " << line.lineName << std::endl;
            std::cout << "Stations: ";
            for (const auto& stop : line.stations) 
            {
                std::cout << stop << " ";
            }
            std::cout << std::endl;
            std::cout << "First Bus Time: " << line.firstBusTime << std::endl;
            std::cout << "Last Bus Time: " << line.lastBusTime << std::endl;
        }
    }
}

// 加载预设路线
void BusSystem::update::addTestRoutes(std::vector<BusLine>& busLines) 
{
    
    // Line D1
    BusLine line1 = {"D1", {"A", "B", "C", "D", "E", "F", "G"},
                        {{{"A", "B"}, 30}, {{"B", "C"}, 5}, {{"C", "D"}, 20}, {{"D", "E"}, 5}, {{"E", "F"}, 20}, {{"F", "G"}, 5}},
                        "06:00", "22:00"};

    BusLine line6 = {"D6", {"G", "F", "E", "D", "C", "B", "A"},
                        {{{"G", "F"}, 5}, {{"F", "E"}, 20}, {{"E", "D"}, 5}, {{"D", "C"}, 20}, {{"C", "B"}, 5}, {{"B", "A"}, 30}},
                        "06:15", "22:15"};

    // Line D2
    BusLine line2 = {"D2", {"T", "C", "R", "Q", "P", "N", "O"},
                        {{{"T", "C"}, 15}, {{"C", "R"}, 20}, {{"R", "Q"}, 5}, {{"Q", "P"}, 10}, {{"P", "N"}, 5}, {{"N", "O"}, 3}},
                        "06:30", "22:30"};
    
    BusLine line7 = {"D7", {"O", "N", "P", "Q", "R", "C", "T"},
                        {{{"O", "N"}, 3}, {{"N", "P"}, 5}, {{"P", "Q"}, 10}, {{"Q", "R"}, 5}, {{"R", "C"}, 20}, {{"C", "T"}, 15}},
                        "06:45", "22:45"};

    // Line D3
    BusLine line3 = {"D3", {"H", "F", "I", "J", "K"},
                        {{{"H", "F"}, 10}, {{"F", "I"}, 15}, {{"I", "J"}, 20}, {{"J", "K"}, 25}},
                        "07:00", "23:00"};
    
    BusLine line8 = {"D8", {"K", "J", "I", "F", "H"},
                        {{{"K", "J"}, 25}, {{"J", "I"}, 20}, {{"I", "F"}, 15}, {{"F", "H"}, 10}},
                        "07:15", "23:15"};

    // Line D4
    BusLine line4 = {"D4", {"W", "R", "X", "U", "Y"},
                        {{{"W", "R"}, 10}, {{"R", "X"}, 15}, {{"X", "U"}, 20}, {{"U", "Y"}, 25}},
                        "07:30", "23:30"};
    
    BusLine line9 = {"D9", {"Y", "U", "X", "R", "W"},
                        {{{"Y", "U"}, 25}, {{"U", "X"}, 20}, {{"X", "R"}, 15}, {{"R", "W"}, 10}},
                        "07:45", "23:45"};

    // Line D5
    BusLine line5 = {"D5", {"V", "U", "N", "M", "L", "J"},
                        {{{"V", "U"}, 12}, {{"U", "N"}, 18}, {{"N", "M"}, 20}, {{"M", "L"}, 22}, {{"L", "J"}, 25}},
                        "08:00", "00:00"};
    
    BusLine line10 = {"D10", {"J", "L", "M", "N", "U", "V"},
                        {{{"J", "L"}, 25}, {{"L", "M"}, 22}, {{"M", "N"}, 20}, {{"N", "U"}, 18}, {{"U", "V"}, 12}},
                        "08:15", "00:15"};

    // Add routes to the system
    busLines = {line1, line6, line2, line7, 
                line3, line8, line4, line9, line5, line10};
    for (const auto& line : busLines) 
    {
        for (const auto& stop : line.stations) 
        {
            BusSystem::routes[stop].push_back(line);
        }
    }
}

// 更新路线
void BusSystem::update::addOrUpdateLine()
{
    BusLine line, reverseLine;
    std::cout << "请输入线路名称: ";
    std::cin >> line.lineName;

    int lineNumber = std::stoi(line.lineName.substr(1));
    reverseLine.lineName = "D" + std::to_string(lineNumber + 5);

    std::cout << "请输入首班车时间: ";
    std::cin >> line.firstBusTime;
    std::cout << "请输入末班车时间: ";
    std::cin >> line.lastBusTime;
    reverseLine.firstBusTime = line.firstBusTime;
    reverseLine.lastBusTime = line.lastBusTime;

    int stopCount;
    std::cout << "请输入站点数量: ";
    std::cin >> stopCount;
    line.stations.resize(stopCount);
    reverseLine.stations.resize(stopCount);

    // 输入双向的站点和行驶时间
    for (int i = 0; i < stopCount; ++i)
    {
        std::cout << "请输入第" << i + 1 << " 个站点: ";
        std::cin >> line.stations[i];
        reverseLine.stations[stopCount - i - 1] = line.stations[i];

        if (i > 0)
        {
            int travelTime;
            std::cout << "请输入从 " << line.stations[i - 1] << " 到 " << line.stations[i] << " 的行驶时间（分钟）: ";
            std::cin >> travelTime;
            line.travelTimes[{line.stations[i - 1], line.stations[i]}] = travelTime;
            reverseLine.travelTimes[{reverseLine.stations[stopCount - i], reverseLine.stations[stopCount - i - 1]}] = travelTime;
        }
    }

    for (const auto& stop : line.stations) BusSystem::routes[stop].push_back(line);
    for (const auto& stop : reverseLine.stations) BusSystem::routes[stop].push_back(reverseLine);

    std::cout << "线路 " << line.lineName << " 及其反向线路 " << reverseLine.lineName << " 已成功添加或更新！\n";

    // 将更改保存到文件
    BusSystem::io::saveRoutesToFile();
}

// 将线路保存到文件
void BusSystem::io::saveRoutesToFile()
{
    std::ofstream outfile("routes.txt");
    if (outfile.is_open())
    {
        for (const auto& routePair : BusSystem::routes)
        {
            for (const auto& line : routePair.second)
            {
                outfile << line.lineName << " " << line.firstBusTime << " " << line.lastBusTime << " " << line.stations.size() << " ";
                for (const auto& stop : line.stations)
                {
                    outfile << stop << " ";
                }
                for (const auto& travelTime : line.travelTimes)
                {
                    outfile << travelTime.first.first << " " << travelTime.first.second << " " << travelTime.second << " ";
                }
                outfile << std::endl;
            }
        }
    }
    outfile.close();
}

// 从文件加载路线
void BusSystem::io::loadRoutesFromFile() 
{
    std::ifstream infile("routes.txt");
    if (infile.is_open()) 
    {
        BusLine line;
        while (infile >> line.lineName >> line.firstBusTime >> line.lastBusTime) 
        {
            int stopCount;
            infile >> stopCount;
            line.stations.resize(stopCount);
            for (int i = 0; i < stopCount; ++i) 
            {
                infile >> line.stations[i];
            }
            std::string stop1, stop2;
            int travelTime;
            while (infile >> stop1 >> stop2 >> travelTime) 
            {
                line.travelTimes[{stop1, stop2}] = travelTime;
            }
            for (const auto& stop : line.stations) 
            {
                BusSystem::routes[stop].push_back(line);
            }
        }
    }
    infile.close();
}

// 管理员菜单
bool BusSystem::user::adminMenu() 
{
    int choice;
    do {
        std::cout << "\n管理员菜单\n";
        std::cout << "1. 添加/更新公交线路\n";
        std::cout << "2. 查询公交线路详情\n";
        std::cout << "3. 查询站点之间的路线\n";
        std::cout << "4. 返回主菜单\n";
        std::cout << "5. 退出程序\n";
        std::cin >> choice;

        if (choice == 5) return false;

        switch (choice) 
        {
            case 1:
                BusSystem::update::addOrUpdateLine();
                break;
            case 2:
                std::cout << BusSystem::algorithm::queryRoutesBetweenStops("A", "G") << std::endl;
                break;
            case 3:
                std::cout << BusSystem::algorithm::queryBusLineDetails("D1") << std::endl;
                break;
            case 4:
                return true;  // Return to main menu
            default:
                std::cout << "无效选项，请重新输入。\n";
        }
    } while (choice != 4);
    return true;
}

// 用户菜单
bool BusSystem::user::userMenu() 
{
    int choice;
    do {
        std::cout << "\n用户菜单\n";
        std::cout << "1. 查询站点之间的路线\n";
        std::cout << "2. 查询公交线路详情\n";
        std::cout << "3. 返回主菜单\n";
        std::cout << "4. 退出程序\n";
        std::cin >> choice;

        if (choice == 4) return false;

        switch (choice) 
        {
            case 1:
                std::cout << BusSystem::algorithm::queryRoutesBetweenStops("A", "G") << std::endl;
                break;
            case 2:
                std::cout << BusSystem::algorithm::queryBusLineDetails("D1") << std::endl;
                break;
            case 3:
                return true; 
            default:
                std::cout << "无效选项，请重新输入。\n";
        }
    } while (choice != 3);
    return true;
}

// 起始登录页
void BusSystem::user::login() 
{
    int userType;
    do {
        std::cout << "\n请选择用户类型:\n1. 普通用户\n2. 管理员\n3. 退出程序\n";
        std::cin >> userType;

        if (userType == 3) 
        {
            std::cout << "退出程序...\n";
            return; 
        }

        switch (userType) 
        {
            case 1:
                if (!BusSystem::user::userMenu()) return;  
                break;
            case 2:
                if (!BusSystem::user::adminMenu()) return;  
                break;
            default:
                std::cout << "无效选项，请重新输入。\n";
        }
    } while (true);
}

// int main() 
// {
//     std::vector<BusLine> busLines;
//     BusSystem system;
//     system.update.addTestRoutes(busLines);  
//     system.user.login();          
//     return 0;
// }
